package test230607;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/7 17:12
 * 1218. 最长定差子序列
 * https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/
 */
public class Solution02 {

    // 纯动态规划, 未进行代码优化, 样例通过 36/39, 超时
    public int longestSubsequence01(int[] arr, int difference) {
        int n = arr.length;
        int[] dp = new int[n];  // dp[i] 表示以 i 位置结尾的定差子序列的最大长度
        Arrays.fill(dp, 1);  // 默认初始值都为 1
        // 动态规划过程
        int maxLen = 1;  // 存储最优解
        for (int i = 1; i < n; ++i) {
            // 由于给定了 difference, 从后往前迭代, 最后一个满足的一定是最长的, 节省循环开销
            for (int j = i - 1; j >= 0; --j) {
                if (arr[j] + difference == arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    break;
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    // 哈希表 + 动态规划
    public int longestSubsequence02(int[] arr, int difference) {
        Map<Integer, Integer> map = new HashMap<>();  // <arr[i], dp[i]>
        int maxLen = 1;  // 存储最优解
        for (int item : arr) {
            map.put(item, map.getOrDefault(item - difference, 0) + 1);
            maxLen = Math.max(maxLen, map.get(item));
        }
        return maxLen;
    }
}
